/*
 * (C) 2012	Sheng Yi
 * A quick sort
 */
#include <stdio.h>

void qsort(int a[], int beg, int end);

int main()
{
	//int test[10] = {2, 6, 8, 1, 9, 4, 5, 7, 12, 3};
	int test[10] = {2, 6, 8, 1, 6, 4, 6, 7, 12, 3};
	int i;
	for (i = 0; i < 10; i++)
		printf("%d ", test[i]);
	printf("\n");
	qsort(test, 0, 9);
	for (i = 0; i < 10; i++)
		printf("%d ", test[i]);
	printf("\n");
	return 0;
}

void qsort(int a[], int beg, int end)
{
		int mid = (beg + end) / 2;
		int val = a[mid];
		int i, j;
		i = beg;
		j = end;
	
		while (i < j)
		{
			// after particition, maybe every part will contain the element equaled val
			// it's OK, we will handle this situation. 
			// After this particition, i must not equal to j
			while (i <= end && a[i] < val)
				i++;
			while (j >= beg && a[j] > val)
				j--;
	
			if (i <= j)	// here, we must handle (i == j)
			{
				int temp = a[i];
				a[i] = a[j];
				a[j] = temp;
				i++;
				j--;
			}
		}

		if (j > beg)
			qsort(a, beg, j);
		if (i < end)
			qsort(a, i, end);
}
